package fun.coding.leetcode;

public class EditDistance {

	public static void main(String[] args) {
		EditDistance ed = new EditDistance();
		String word1 = "abc";
		String word2 = "bc";
		String w3 = "baozi";
		String w4 = "boi";
		
		assert ed.minDistance(word1, word2) == 1;
		assert ed.minDistance(w3, w4) == 2;
		System.out.println(ed.minDistance(word1, word2));
	}
	
	public int minDistance(String word1, String word2) {
		if (word1 == null || word2 == null) return -1;
		
		int l1 = word1.length();
		int l2 = word2.length();
		
		if (l1 == 0 || l2 == 0) {
			return l1 == 0 ? l2 : l1;
		}
		
		// A pattern for coding up DP, use extra array
		// This could be further optimized into 2 arrays
		int[][] lookup = new int[l1+1][l2+1];
		
		// Note the initialization case here, for an empty string, it will take i to change with the current one
		for (int i = 0; i <= l2; i++) {
			lookup[0][i] = i;
		}
		
		for (int i = 0; i <= l1;i++) {
			lookup[i][0] = i;
		}
		
		/*
		 * dp[i][j] =  dp[i-1][j-1]   if (A[i] == B[j])
           or = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) +1;
       		dp[0][j] = j and dp[i][0] = i   */
		// this is O(M*N) time and M*N space, space could be saved using 2 arrays
		for (int i = 1; i <= l1; i++) {
			for (int j = 1; j <= l2; j++) {
				if (word1.charAt(i-1) == word2.charAt(j-1)) {
					lookup[i][j] = lookup[i-1][j-1];
				} else {
					lookup[i][j] = Math.min(lookup[i-1][j], Math.min(lookup[i][j-1], lookup[i-1][j-1])) + 1;
				}
			}
		}
		
		return lookup[l1][l2];
    }

}
